package fina.indextree;

import thired.class20_indextree.Class01_IndexTree;

// 下标 +/- 最右侧的1 add+  sum-
public class IndexTree {
    int[] sum;
    int[] arr;
    int MAXN;
    public IndexTree(int N) {
        MAXN = N + 1;
        arr = new int[MAXN];
//        for (int i = 1; i < MAXN; i++) {
//            arr[i] = nums[i - 1];
//        }
        sum = new int[MAXN];
    }
    public void build(){
        for(int index = 1;index < MAXN; index++){
            int ind = index;
            while(ind <= MAXN){
                sum[index] += sum[ind];
                ind += (ind & -ind);
            }
        }
    }
    public void add(int index, int val){
        while (index <= MAXN){
            sum[index] += val;
            index += (index & -index);
        }
    }
    public int sum(int index){
        int res = 0;
        while (index > 0){
            res += sum[index];
            index -= (index & -index);
        }
        return res;
    }

    public static class Right {
        private int[] nums;
        private int N;

        public Right(int size) {
            N = size + 1;
            nums = new int[N + 1];
        }

        public int sum(int index) {
            int ret = 0;
            for (int i = 1; i <= index; i++) {
                ret += nums[i];
            }
            return ret;
        }

        public void add(int index, int d) {
            nums[index] += d;
        }

    }

    public static void main(String[] args) {
        int N = 100;
        int V = 100;
        int testTime = 2000000;
        IndexTree tree = new IndexTree(N);
        Right test = new Right(N);
        System.out.println("test begin");
        for (int i = 0; i < testTime; i++) {
            int index = (int) (Math.random() * N) + 1;
            if (Math.random() <= 0.5) {
                int add = (int) (Math.random() * V);
                tree.add(index, add);
                test.add(index, add);
            } else {
                if (tree.sum(index) != test.sum(index)) {
                    System.out.println("Oops!");
                }
            }
        }
        System.out.println("test finish");
    }
}
